/**
 * 
 */
package leetCode;

import java.util.HashMap;

/**
 * MapSum class with insert, and sum methods. insert(str,int)——如果存在就覆盖
 * sum(str前缀） 维护一颗前缀树
 * 
 * @author zhongfang
 *
 */
public class MapSumPairs {
	class Node {
		int val;
		boolean isEnd;
		Node parent;
		HashMap<Character, Node> childs = new HashMap<>();
	}

	Node root;

	public MapSumPairs() {
		root = new Node();
	}

	public void insert(String key, int val) {
		Node curNode = root;
		for (int i = 0; i < key.length(); i++) {
			char ch = key.charAt(i);
			if (curNode.childs.containsKey(ch)) {
				curNode = curNode.childs.get(ch);
			} else {
				Node newNode = new Node();
				newNode.parent = curNode;
				curNode.childs.put(ch, newNode);
				curNode = newNode;
			}
		}
		int diff = 0;
		if (curNode.isEnd) {// 已经存在，则覆盖
			diff = val - curNode.val;// 变化值
		} else {
			curNode.isEnd = true;
			diff = val;
		}
		while (curNode.parent != null) {
			curNode.val += diff;
			curNode = curNode.parent;
		}
	}

	public int sum(String prefix) {
		Node curNode = root;
		for (int i = 0; i < prefix.length(); i++) {
			char ch = prefix.charAt(i);
			if (curNode.childs.containsKey(ch)) {
				curNode = curNode.childs.get(ch);
			} else {
				return 0;
			}
		}
		return curNode.val;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MapSumPairs pairs = new MapSumPairs();
		pairs.insert("apple", 3);
		System.out.println(pairs.sum("ap"));
		pairs.insert("app", 2);
		System.out.println(pairs.sum("ap"));
	}
}
